#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1.5e5 + 5;
const int K = 1e6 + 5;

int n, m;
int a[N];
int pos[N];
struct Update {
  int pos, v0, v1;
} u[N];
struct Query {
  int l, r, t, id;
  bool operator<(Query x) const {
    if (pos[l] != pos[x.l]) return l < x.l;
    if (pos[r] != pos[x.r]) return r < x.r;
    return t < x.t;
  }
} q[N];
int unum, qnum, ans[N];
int cnt[K];
int tot, l = 1, r;
void init() {
  int k = pow(n, 2.0 / 3.0);
  rep(i, 1, n) pos[i] = (i - 1) / k + 1;
}
void add(int x) {
  cnt[x]++;
  if (cnt[x] == 1) tot++;
}
void del(int x) {
  cnt[x]--;
  if (cnt[x] == 0) tot--;
}
void forward(int t) {
  a[u[t].pos] = u[t].v1;
  if (u[t].pos >= l && u[t].pos <= r) {
    del(u[t].v0);
    add(u[t].v1);
  }
}
void backward(int t) {
  a[u[t].pos] = u[t].v0;
  if (u[t].pos >= l && u[t].pos <= r) {
    del(u[t].v1);
    add(u[t].v0);
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, m) {
    char op;
    int x, y;
    cin >> op >> x >> y;
    if (op == 'Q') {
      qnum++;
      q[qnum] = Query{x, y, unum, qnum};
    } else {
      u[++unum] = Update{x, a[x], y};
      a[x] = y;
    }
  }
  init();
  sort(q + 1, q + qnum + 1);
  int t = unum;
  rep(i, 1, qnum) {
    while (t > q[i].t) backward(t--);
    while (t < q[i].t) forward(++t);
    while (r > q[i].r) del(a[r--]);
    while (r < q[i].r) add(a[++r]);
    while (l < q[i].l) del(a[l++]);
    while (l > q[i].l) add(a[--l]);
    ans[q[i].id] = tot;
  }
  rep(i, 1, qnum) cout << ans[i] << endl;
  return 0;
}